package org.geekbang.time.mathbasicthought.lesson6_recursive;

import java.util.Arrays;

public class MergeSort {
    static int[] toSort = {1, 4, 7, 3, 2, 9, 0, 5, 6, 8};

    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(toSort)));
    }

    public static int[] mergeSort(int[] toSort) {
        if (toSort.length == 1)
            return toSort;

        int[] left = Arrays.copyOfRange(toSort, 0, toSort.length / 2);
        int[] right = Arrays.copyOfRange(toSort, toSort.length / 2, toSort.length);

        int[] sortedLeft = mergeSort(left);
        int[] sortedRight = mergeSort(right);
        int[] sordedAll = merge(sortedLeft, sortedRight);

        return sordedAll;
    }

    private static int[] merge(int[] sortedLeft, int[] sortedRight) {
        int[] result = new int[sortedLeft.length + sortedRight.length];

        int leftIndex = 0, rightIndex = 0, resultIndex = 0;
        while (leftIndex < sortedLeft.length && rightIndex < sortedRight.length) {
            if (sortedLeft[leftIndex] <= sortedRight[rightIndex]) {
                result[resultIndex] = sortedLeft[leftIndex];
                leftIndex++;
            } else {
                result[resultIndex] = sortedRight[rightIndex];
                rightIndex++;
            }
            resultIndex++;
        }

        if (leftIndex < sortedLeft.length) {
            for (int i = leftIndex; i < sortedLeft.length; i++) {
                result[resultIndex] = sortedLeft[i];
                resultIndex++;
            }
        } else {
            for (int i = rightIndex; i < sortedRight.length; i++) {
                result[resultIndex] = sortedRight[i];
                resultIndex++;
            }
        }

        return result;
    }
}
